package LinkedList;

///**
// * 代码实现链表——节点类
// */
//class Node {
//    Object data;//数据域
//    //...
//    Node next;//节点
//
//    //节点的构造方法：初始化数据域，将节点指向空
//    public Node(Object data) {
//        this.data = data;
//        this.next = null;
//    }
//}
//
///**
// * 代码实现链表
// */
//public class LinkedList {
//    private Node first;
//    private Node last;
//    //链表的方法:判空，添加节点，删除节点等
//    //...
//}

import java.util.Stack;

/**
 * 代码实现单向链表——节点类
 */
class Node {
    int bookId;//书籍序列号
    String bookName;//书籍名称
    Node next;//节点

    //节点的构造方法：初始化数据域，将节点指向空
    public Node(int bookId, String bookName) {
        this.bookId = bookId;
        this.bookName = bookName;
        this.next = null;
    }
}

/**
 * 代码实现链表
 */
public class LinkedList {
    private Node first;
    private Node last;

    //判空
    public boolean isEmpty() {
        return first == null;//布尔表达式，头节点空返回true，反之返回false
    }

    //打印链表(从链表头打印到链表尾)
    public void printLinkedList() {
        Node current = first;//定义一个暂时的节点，赋值为头节点
        while (current != null) {
            System.out.println(current.bookId + current.bookName);
            current = current.next;
        }
    }

    //在尾部添加节点
    public void addNode(Node newNode) {
        if (this.isEmpty()) {//链表为空时，插入节点(头尾节点均为新节点)
            first = newNode;
            last = newNode;
        } else {//链表不为空时，以下两个语句不可颠倒，否则之前的尾节点会被覆盖。
            last.next = newNode;//新节点赋值为 当前尾节点的下一节点
            last = newNode;//此时链表的尾节点 为刚插入的新节点
        }
    }

    //删除节点 分为三种情况：删除的节点为头节点，删除的节点为尾节点，删除的为中间的某个节点。
    public void delete(Node needDeleteNode) {
        Node newNode;
        Node tempNode;
        //1.删除的节点为头节点
        if (first.bookId == needDeleteNode.bookId) {
            first = first.next;//新头节点赋值为原始头结点的下一个节点
        } else if (last.bookId == needDeleteNode.bookId) {
            //2.删除的节点为尾节点//需要先遍历节点至 尾节点的前一个节点
            newNode = first;
            while (newNode.next != last) newNode = newNode.next;//直至newNode为尾节点的前一个节点
            newNode.next = last.next;//原尾节点的前一个节点 的next节点置空(其实就是原尾节点失去指向)
            last = newNode;//新尾节点为 原尾节点的前一个节点
        } else {//3.删除的为中间的某个节点。需要知道需删除节点的前一节点
            newNode = first;
            tempNode = first;
            while (newNode.bookId != needDeleteNode.bookId) {//遍历链表至newNode为needDeleteNode
                tempNode = newNode;//tempNode暂存newNode
                newNode = newNode.next;
                //循环结束时tempNode为newNode前一个节点
            }
            //循环结束：
            // newNode为needDeleteNode
            // tempNode为newNode的前一节点，即needDeleteNode的迁移节点
            //删除节点即：需删除节点的前一节点指向需删除节点的后一节点
            tempNode.next = needDeleteNode.next;
        }
    }

    //插入节点：三种情况：插入的节点为头节点，插入的节点为尾节点，插入的为中间的某个节点。
    //传入的节点needInsertNode 数据域与节点域均已初始化 固可根据needInsertNode.next判断
    public void insertNode(Node needInsertNode) {
        Node tempNode;
        Node newNode;
        if (this.isEmpty()) {//原链表空，插头插尾都一样 头尾均为新节点
            first = needInsertNode;
            last = needInsertNode;
        } else {
            if (needInsertNode.next == first) {//1.原链表非空，插头
                first = needInsertNode;//新头节点为needInsertNode
            } else if (needInsertNode.next == null) {//2.原链表非空。插尾
                last.next = needInsertNode;//原尾节点的下一节点为新插入节点
                last = needInsertNode;//新尾节点为新插入节点
            } else {//3.插中间 需要得到待插入节点的前一节点
                // （后一节点已知：即传入的Node类型参数的next属性）
                // 即needInsertNode的next节点(已知) 的前一节点
                newNode = first;
                tempNode = first;
                while (needInsertNode.next != newNode.next) {//遍历链表至newNode.next为needInsertNode.next
                    tempNode = newNode;//temp暂存newNode
                    newNode = newNode.next;
                    //循环结束时tempNode为newNode前一个节点
                }
                //循环结束：
                // needInsertNode.next = newNode.next，即 newNode=needInsertNode
                // tempNode=newNode的前一节点，即needInsertNode的前一节点
                //所以得到了待插入节点的前一节点
                tempNode.next = needInsertNode;
                needInsertNode.next = newNode;
            }
        }
    }


    //leetcode206反转链表

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    //     //方法：链表的反转 栈解决 效率低 3ms 37.1MB
    //    public ListNode reverseList(ListNode head) {
    //        if(head==null||head.next==null) return head;
    //        Stack<ListNode> stack= new Stack<>();
    //        ListNode current=head;
    //        while (current!=null){
    //            stack.push(current);
    //            current=current.next;
    //        }
    //        ListNode newHead=stack.pop();
    //        ListNode currentNode=newHead;
    //        while (!stack.empty()){
    //            ListNode tempNode=stack.pop();
    //            tempNode.next=null;
    //            currentNode.next = tempNode;
    //            currentNode=currentNode.next;
    //        }
    //        return newHead;
    //    }
    //方法：链表的反转 栈解决
    public Node reverseListByStack(Node head) {
        Stack<Node> stack = new Stack<>();
        Node current = head;
        while (current != null) {
            System.out.println("压栈" + current.bookId + current.bookName);
            stack.push(current);
            current = current.next;
        }
        LinkedList linkedList = new LinkedList();
        linkedList.first = stack.pop();
        Node currentNode = linkedList.first;
        while (!stack.empty()) {
            Node tempNode = stack.pop();
            tempNode.next = null;
            currentNode.next = tempNode;
            currentNode = currentNode.next;
        }
//        linkedList.printLinkedList();
        return linkedList.first;
    }

    /**
     * 链表的反转
     *
     * @param head 头节点
     * @return reverseHead 反转后新链表的表头
     */
    public static Node reverseList(Node head) {
        //如果链表为空或者只有一个节点，无需反转，直接返回原链表的头结点
        if (head == null || head.next == null) return head;
        Node current = head;
        Node next; //定义当前结点的下一个结点
        Node reverseHead = null;  //反转后新链表的表头
        while (current != null) {
            next = current.next;  //暂时保存住当前结点的下一个结点，因为下一次要用
            current.next = reverseHead; //将current的下一个结点指向新链表的头结点
            reverseHead = current;
            current = next;   // 操作结束后，current节点后移
        }
        return reverseHead;
    }
//————————————————
//    版权声明：本文为CSDN博主「HSXaaa123」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
//    原文链接：https://blog.csdn.net/weixin_41924879/article/details/100065905

    //反转链表 书上的方法
    public void reversePrintLinkedList() {
        if (first == null || first.next == null) return;
        Node current = first;
        Node before = null;
        while (current != null) {
            last = before;
            before = current;
            current = current.next;
            before.next = last;
        }
        current = before;
        while (current != null) {
            System.out.println(current.bookId + current.bookName);
            current = current.next;
        }
    }

    //单链表的串联
    public LinkedList ConnectLinkedList(LinkedList linkedList, LinkedList linkedList2) {
        linkedList.last.next = linkedList2.first;
        return linkedList;
    }


    //单向链表测试
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        Node node1 = new Node(12086, "《数据结构》");
        Node node2 = new Node(18002, "《计算机网络》");
        Node node3 = new Node(19121, "《数据库概论》");
        Node node5 = new Node(39991, "《设计模式》");
        Node node6 = new Node(34171, "《Springboot》");
        linkedList.addNode(node1);
        linkedList.addNode(node2);
        linkedList.addNode(node3);
        LinkedList linkedList2 = new LinkedList();//测试链表链接
        linkedList2.addNode(node5);
        linkedList2.addNode(node6);

        System.out.println("单向链表为空？" + linkedList.isEmpty());
        linkedList.printLinkedList();

        //测试插入
        System.out.println("测试插入");
        Node node4 = new Node(20918, "《操作系统》");
        //需要初始化节点的next属性
        // node4.next=linkedList.first;//插头
        node4.next = node3;//插中间 例如插到node3之前
        // node4.next = null;//插尾
        linkedList.insertNode(node4);
        linkedList.printLinkedList();

        //测试删除
        System.out.println("测试删除");
        //linkedList.delete(linkedList.first);//删头
        //linkedList.delete(linkedList.last);//删尾
        linkedList.delete(node3);//删中间
        linkedList.printLinkedList();

        //测试单向链表的反转
        //System.out.println("测试单向链表的反转 将结果打印");
//        Node reverseHeadNode = linkedList.reverseList(linkedList.first);
//        while (reverseHeadNode != null) {
//            System.out.println(reverseHeadNode.bookId + reverseHeadNode.bookName);
//            reverseHeadNode = reverseHeadNode.next;
//        }
        //书上的方法
        //linkedList.reversePrintLinkedList();//书上的方法
        // System.out.println(linkedList.first.bookId + linkedList.first.bookName);
        //Node newHeadNode = linkedList.reverseListByStack(linkedList.first);
//        while (newHeadNode!=null){
//            System.out.println(newHeadNode.bookId+newHeadNode.bookName);
//            newHeadNode=newHeadNode.next;
//        }
        System.out.println("测试串联");
        System.out.println("串联链表一");
        linkedList.printLinkedList();
        System.out.println("串联链表二");
        linkedList2.printLinkedList();
        LinkedList newLinkedList = linkedList.ConnectLinkedList(linkedList, linkedList2);
        System.out.println("串联结果");
        newLinkedList.printLinkedList();

    }


}